#ifndef __LINKTREE_H_
#define __LINKTREE_H_
#include <string>
#include "DynamicArray.hpp"


template<typename T >
class TreeNode
{
public:
    TreeNode(const T &element);
    void Connect(TreeNode<T> *parent);
    void DisConnect(TreeNode<T> *parent);
    
    static void FreeNode(TreeNode<T> *node);

    void show(TreeNode<T> *node, int depth) ;

    static int GetNodeHigh(const TreeNode<T>* node);

    static TreeNode<T>* FindNode(TreeNode<T>* node, const T& element);
    // static void FindNode(TreeNode<T>* node, const T& element, DARRAY::DynamicArray& a)
    // {
    //     if (node == nullptr) 
    //         return;
    //     if (node->data == element && node->parent != nullptr) 
    //         a.InsertTail(node);
    //     FindNode(node->FirstChild, element, a);
    //     FindNode(node->nextSbling, element, a);
    // }

    TreeNode<T>* GetParent();
    const T& GetData();
    void SetData(const T &element);

private:
    T data;
    TreeNode<T> *parent;
    TreeNode<T> *FirstChild;
    TreeNode<T> *nextSibling;
};

template<typename T >
class LinkTree 
{
public:
    LinkTree(): root(new TreeNode<T>(T())) {}

    LinkTree(const T& element): root(new TreeNode<T>(element)){}

    ~LinkTree()
    {
        TreeNode<T>::FreeNode(root);
    }

    TreeNode<T> * GetRoot()
    {
        return root;
    }

    void show() 
    {
        root->show(root, 0); 
    }

    DARRAY::DynamicArray<T> FindByElement(const T& element) 
    {
        DARRAY::DynamicArray<T> a;
        TreeNode<T>::FindNode(root, element, a);
        return a;
    }

    int GetTreeHigh() const
    {
        return TreeNode<T>::GetNodeHigh(root) - 1; 
    }

    std::string GetNodePath(TreeNode<T> *node) const
    {
        if (node == nullptr)
        {
            return std::string();
        }

        std::string path = node->GetData();
        while (node->GetParent() != nullptr)
        {
            path = node->GetParent()->GetData() + "/" + path;
            node = node->GetParent();
        }
        return path;
    }

private:
    TreeNode<T> *root;
};


template <typename T>
inline TreeNode<T>::TreeNode(const T &element): data(element), parent(nullptr), FirstChild(nullptr), nextSibling(nullptr)
{
}

template <typename T>
inline void TreeNode<T>::Connect(TreeNode<T> *parent)
{
    if (!parent) return;
    this->parent = parent;
    this->nextSibling = parent->FirstChild;
    parent->FirstChild = this;
}

template <typename T>
inline void TreeNode<T>::DisConnect(TreeNode<T> *parent)
{
    if (!parent || this->parent != parent) return;

    TreeNode<T> *travelPoint = parent->FirstChild;
    if (this == parent->FirstChild) 
    {
        parent->FirstChild = this->nextSibling;
    }
    else
    {
        while (travelPoint->nextSibling != nullptr)
        {
            if (travelPoint->nextSibling == this)
            {
                travelPoint->nextSibling = this->nextSibling;
                break;
            }
            travelPoint = travelPoint->nextSibling;
        }
    }
    this->parent = this->nextSibling = nullptr;
}

template <typename T>
inline void TreeNode<T>::FreeNode(TreeNode<T> *node)
{
    if (node == nullptr) return;
    FreeNode(node->FirstChild);
    FreeNode(node->nextSibling);
    delete node;
}

template <typename T>
inline void TreeNode<T>::show(TreeNode<T> *node, int depth)
{
    if (node == nullptr) return;
    
    for (int i = 0; i < depth; i++)
    {
        std::cout << " ";
    }
    
    if (depth > 0)
    {
        std::cout << "|_";
    }

    std::cout << node->data << std::endl;

    show(node->FirstChild, depth + 1);
    show(node->nextSibling, depth);
}

template <typename T>
inline TreeNode<T> *TreeNode<T>::FindNode(TreeNode<T> *node, const T &element)
{
    if (node == nullptr) return nullptr;
    if (node->data == element && node->parent != nullptr) return node;
    
    TreeNode<T> *target = FindNode(node->FirstChild, element);
    if (target) return target;
    
    return FindNode(node->nextSibling, element);
}

template <typename T>
inline TreeNode<T> *TreeNode<T>::GetParent()
{
    return parent;
}

template <typename T>
inline const T& TreeNode<T>::GetData()
{
    return data;
}

template <typename T>
inline void TreeNode<T>::SetData(const T &element)
{
    data = element;
}

template <typename T>
inline int TreeNode<T>::GetNodeHigh(const TreeNode<T> *node)
{
    if (node == nullptr) return 0;
    int Maxhigh = 0;
    TreeNode<T> *travelPoint = node->FirstChild;
    while (travelPoint != nullptr)
    {
        int high = GetNodeHigh(travelPoint);
        Maxhigh = std::max(Maxhigh, high);
        travelPoint = travelPoint->nextSibling;
    }
    return Maxhigh + 1;
}


#endif


